Lý thuyết về chứng minh có thể kiểm chứng ngẫu nhiên nghiên cứu về khả năng của hệ thống kiểm chứng ngẫu nhiên với các giá trị tham số khác nhau (tham số toàn vẹn, tham số đúng đắn, số bit ngẫu nhiên, số bit của chứng minh, kích thước bảng chữ cái). Lý thuyết này có nhiều ứng dụng trong lý thuyết độ phức tạp tính toán (đặc biệt là chứng minh sự không xấp xỉ được), và mật mã học.

Định nghĩa của chứng minh có thể kiểm chứng ngẫu nhiên được đưa ra bởi Arora và Safra năm 1992[1], tuy nhiên các tính chất của chúng đã được nghiên cứu từ trước. Năm 1990, Babai, Fortnow, và Lund đã chứng minh PCP ( p o l y ( n ) , p o l y ( n ) ) = {\displaystyle (poly(n),poly(n))=} NEXP, đưa ra sự tương đương đầu tiên giữa chứng minh thông thường (NEXP) và chứng minh có thể kiểm chứng ngẫu nhiên. Định lý PCP năm 1992 chứng minh rằng PCP O ( log ⁡ n ) , O ( 1 ) ) = {\displaystyle O(\log n),O(1))=} NP.